package com.mashibing.class13;

import java.util.*;

/**
 * 贪心算法.
 */
public class Code05_LowestLexicography {

    public static String lowestString1(String[] strs){
        if (strs==null||strs.length==0){
            return "";
        }
        TreeSet<String> ans = process(strs);
        return ans.size()==0 ? "" : ans.first();
    }

    // strs中所有字符串全排列,返回所有可能的结果
    public static TreeSet<String> process(String[] strs){
        TreeSet<String> ans = new TreeSet<String>();
        if (strs.length==0){
            ans.add("");
            return ans;
        }
        for (int i = 0; i < strs.length; i++) {
            String first = strs[i]; // 我的第一个字符串.
            String[] nexts = removeIndexString(strs, i); // 除掉first 字符串 还有那些字符串.
            // 除first字符串之后 其余可能结果的集合.
            TreeSet<String> next = process(nexts);
            // 所有的可能结果 与 first 进行组合.
            for (String cur : next) {
                ans.add(first+cur);
            }
        }
        for (String cur : ans) {
            System.out.print(cur+",");
        }
        System.out.println();
        return ans;
    }
    //{"abc","cks","bct"}
    // 0      1     2
    // removeIndexString(arr,1) -> {"abc","bct"}
    public static String[] removeIndexString(String[] arr, int index){
        int N = arr.length;
        String[] ans = new String[N - 1];
        int ansIndex = 0;
        for (int i = 0; i < N; i++) {
            if (i!=index){
                ans[ansIndex++] = arr[i];
            }
        }
        return ans;
    }


    public static class MyComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            // a拼接b 和 b拼接a 字符串进行比较.
            return (a + b).compareTo(b + a);
        }
    }

    public static String lowestString2(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        Arrays.sort(strs, new MyComparator());
        String res = "";
        for (int i = 0; i < strs.length; i++) {
            res += strs[i];
        }
        return res;
    }

    // for test
    public static String generateRandomString(int strLen) {
        char[] ans = new char[(int) (Math.random() * strLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            int value = (int) (Math.random() * 5);
            ans[i] = (Math.random() <= 0.5) ? (char) (65 + value) : (char) (97 + value);
        }
        return String.valueOf(ans);
    }

    // for test
    public static String[] generateRandomStringArray(int arrLen, int strLen) {
        String[] ans = new String[(int) (Math.random() * arrLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = generateRandomString(strLen);
        }
        return ans;
    }

    // for test
    public static String[] copyStringArray(String[] arr) {
        String[] ans = new String[arr.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = String.valueOf(arr[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        int arrLen = 6;
        int strLen = 5;
        int testTimes = 1;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String[] arr1 = generateRandomStringArray(arrLen, strLen);
            String[] arr2 = copyStringArray(arr1);
            if (!lowestString1(arr1).equals(lowestString2(arr2))) {
                for (String str : arr1) {
                    System.out.print(str + ",");
                }
                System.out.println();
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
}
